package BFS;

import java.util.*;

/**
 * @Author: biubiu0002
 * @Date: 2021-04-01 16:09
 **/
//一次移动 有八种情况，每种情况又有八种情况

public class 解开密码锁的最小次数 {

    public int openLock(String[] deadends, String target) {
        Queue<String> q = new LinkedList<>();
        Set<String> memo = new HashSet();
        Set<String> deads = new HashSet<>();
        for(String s:deadends) deads.add(s);
        q.offer("0000");
        memo.add("0000");

        int step = 0;
        while(!q.isEmpty()){
            int sz = q.size();
            for(int i=0;i<sz;i++){
                String cur = q.poll();
                //判断是否是target
                if(cur.equals(target))
                    return step;
                //判断cur是否到了deadends
                if(deads.contains(cur))
                    continue;
                //把相邻节点加入到queue
                for(int j=0;j<4;j++){
                    String up = plusOne(cur,j);
                    String down = plusOne(cur,j);
                    if(!memo.contains(up)){
                        q.offer(up);
                        memo.add(up);
                    }
                    if(!memo.contains(down)){
                        q.offer(down);
                        memo.add(down);
                    }
                }
            }
            step++;
        }
        return step;

    }

    String plusOne(String cur,int i){
        char[] chs = cur.toCharArray();
        if(chs[i]=='9')
            chs[i]='0';
        else
            chs[i]+=1;
        return new String(chs);

    }
    String minusOne(String cur,int i){
        char[] chs = cur.toCharArray();
        if(chs[i]=='0')
            chs[i]='9';
        else
            chs[i]-=1;
        return new String(chs);

    }

}
